home *** CD-ROM | disk | FTP | other *** search
/ TOS Silver 2000 / TOS Silver 2000.iso / Spiele / GEMSPIEL / GEMAMIGO / SRC / AMIGO.C next >
Encoding:
C/C++ Source or Header  |  1998-10-29  |  14.1 KB  |  654 lines
  1. /* Go started 4/17/88 by Todd R. Johnson */
  2. /* 8/8/89 cleaned up for first release */
  3. /* Public Domain */
  4.  
  5. #include "go.h"
  6. #include "amigo.h"
  7.  
  8.  
  9. extern char    *playReason;
  10. extern short    playLevel, showTrees;
  11.  
  12. struct bRec    goboard[19][19];    /*-- The main go board        --*/
  13.  
  14. struct Group    GroupList[MAXGROUPS];    /*-- The list of Groups        --*/
  15. short        DeletedGroups[4];    /*-- Codes of deleted groups    --*/
  16.  
  17. short        GroupCount = 0;        /*-- The total number of groups    --*/
  18. short        DeletedGroupCount;    /*-- The total number of groups    --*/
  19.                     /*-- deleted on a move        --*/
  20. short        ko, koX, koY;
  21. short        blackTerritory,whiteTerritory;
  22. short        blackPrisoners, whitePrisoners;
  23. short        showMoveReason    = FALSE,
  24.         groupInfo    = FALSE,
  25.         whitePassed    = FALSE,
  26.         blackPassed    = FALSE;
  27.  
  28.  
  29. /* Arrays for use when checking around a point */
  30. short        xVec[4] = {0, 1, 0, -1};
  31. short        yVec[4] = {-1, 0, 1, 0};
  32.  
  33. short
  34. member(group, grouplist, cnt)
  35.     short        group;
  36.     short        grouplist[4];
  37.     short        cnt;
  38. {
  39.     unsigned short    i;
  40.  
  41.  
  42.     for (i = 0; i < cnt; i++)
  43.         if (grouplist[i] == group)
  44.             return TRUE;
  45.     return FALSE;
  46. }
  47.  
  48. /* Does a stone at x, y connect to any groups of color? */
  49. short
  50. Connect( color, x, y, fGroups, fCnt, eGroups, eCnt)
  51.     enum bVal    color;
  52.     short        x, y;
  53.     short        fGroups[4], eGroups[4];
  54.     short        *fCnt, *eCnt;
  55. {
  56.     unsigned short    point = 0;
  57.     short        tx, ty, total = 0;
  58.     enum bVal    opcolor = WHITE;
  59.  
  60.  
  61.     *fCnt = 0;
  62.     *eCnt = 0;
  63.     if (color == WHITE)
  64.         opcolor = BLACK;
  65.     for (point = 0; point <= 3; point++ )  
  66.     {
  67.         tx = x + xVec[point];
  68.         ty = y + yVec[point];
  69.         if (!LegalPoint(tx,ty))
  70.             continue;
  71.         if (goboard[tx][ty].Val == color)
  72.         {
  73.             total++;
  74.             if (!member(goboard[tx][ty].GroupNum, fGroups, *fCnt))
  75.                 fGroups[(*fCnt)++] = goboard[tx][ty].GroupNum;
  76.         }
  77.         else if (goboard[tx][ty].Val == opcolor)
  78.         {
  79.             total++;
  80.             if (!member(goboard[tx][ty].GroupNum, eGroups, *eCnt))
  81.                 eGroups[(*eCnt)++] = goboard[tx][ty].GroupNum;
  82.         }
  83.     }
  84.     return total;
  85. }
  86.  
  87. /* Returns the maximum number of liberties for a given intersection */
  88. short
  89. Maxlibs(x, y)
  90.     short    x, y;
  91. {
  92.     short    cnt = 4;
  93.  
  94.  
  95.     if (x == 0 || x == 18)
  96.         cnt--;
  97.     if (y == 0 || y == 18)
  98.         cnt--;
  99.     return cnt;
  100. }
  101.  
  102. DeleteGroupFromStone(x,y)
  103.     short    x,y;
  104. {
  105.     if (goboard[x][y].Val != EMPTY)
  106.         GroupCapture(goboard[x][y].GroupNum);
  107. }
  108.  
  109. /* Determine whether x, y is suicide for color */
  110. short
  111. Suicide(color, x, y)
  112.     enum bVal    color;
  113.     short        x, y;
  114. {
  115.     enum bVal    opcolor = BLACK;
  116.     short        friendlycnt, friendlygroups[4],
  117.             enemycnt, enemygroups[4],
  118.             total;
  119.     short        maxlibs, i, libcnt = 0;
  120.  
  121.  
  122.     if (color == BLACK)
  123.         opcolor = WHITE;
  124.     maxlibs = Maxlibs( x, y);
  125.     total = Connect(color, x, y, friendlygroups, &friendlycnt,
  126.                     enemygroups, &enemycnt);
  127.  
  128.     if (total < maxlibs)
  129.         return FALSE;
  130.  
  131.     /* Check for a capture */
  132.     for (i = 0; i < enemycnt; i++)
  133.         if (GroupList[enemygroups[i]].liberties == 1)
  134.             return FALSE;
  135.     for (i = 0; i < friendlycnt; i++)
  136.         libcnt += (GroupList[friendlygroups[i]].liberties - 1);
  137.     if (libcnt != 0)
  138.         return FALSE;
  139.     return TRUE;
  140. }
  141.    
  142. /* Returns the number of liberties for x, y */
  143. short
  144. StoneLibs(x, y)
  145.     short        x, y;
  146. {
  147.     short        cnt = 0, tx, ty;
  148.     unsigned short    point;
  149.  
  150.  
  151.     for (point = 0; point <= 3; point++)
  152.     {
  153.         tx = x + xVec[point];
  154.         ty = y + yVec[point];
  155.         if (LegalPoint(tx,ty) && goboard[tx][ty].Val == EMPTY)
  156.             cnt++;
  157.     }
  158.     return cnt;
  159. }
  160.    
  161. void
  162. EraseMarks()
  163. {
  164.     register short        i;
  165.     register struct bRec    *gpt    = &goboard[0][0];
  166.  
  167.  
  168.     for (i=0; i<361; gpt++,i++)
  169.             gpt->marked = FALSE;
  170. }
  171.  
  172. /* Place a stone of color at x, y */
  173. short
  174. GoPlaceStone(color, x, y)
  175.     enum bVal    color;
  176.     short        x, y;
  177. {
  178.     short    fgroups[4], egroups[4];    /* group codes surrounding stone */
  179.     short    fcnt, ecnt, i;
  180.     short    lowest = GroupCount + 1;
  181.  
  182.  
  183.     DeletedGroupCount = 0;
  184.     if (goboard[x][y].Val != EMPTY || Suicide(color,x,y))
  185.         return FALSE;
  186.  
  187.     if (ko && koX == x && koY == y)
  188.         return FALSE;
  189.  
  190.     ko = FALSE;
  191.     placestone(color, x, y);
  192.     goboard[x][y].Val = color;
  193.     /* Does the new stone connect to any friendly stone(s)? */
  194.     Connect(color, x, y, fgroups, &fcnt, egroups, &ecnt);
  195.     if (fcnt)
  196.     {
  197.         /* Find the connecting friendly group with the lowest code */
  198.         for (i = 0; i < fcnt; i++)
  199.             if (fgroups[i] <= lowest)
  200.                 lowest = fgroups[i];
  201.         /*-- Renumber resulting group --*/
  202.         /*-- Raise the stone count of the lowest by one to account --*/
  203.         /*-- for new stone --*/
  204.         goboard[x][y].GroupNum = lowest;
  205.         GroupList[lowest].count++;
  206.         for (i = 0; i < fcnt; i++)
  207.             if (fgroups[i] != lowest)
  208.                 MergeGroups(lowest, fgroups[i]);
  209.         /* Fix the liberties of the resulting group */
  210.         CountLiberties(lowest);
  211.     }
  212.     else
  213.     {
  214.         /* Isolated stone.  Create new group. */
  215.         GroupCount++;
  216.         lowest = GroupCount;
  217.         GroupList[lowest].color = color;
  218.         GroupList[lowest].count = 1;
  219.         GroupList[lowest].internal = 0;
  220.         GroupList[lowest].external = StoneLibs( x, y);
  221.         GroupList[lowest].liberties = GroupList[lowest].external;
  222.         GroupList[lowest].eyes = 0;
  223.         GroupList[lowest].alive = 0;
  224.         GroupList[lowest].territory = 0;
  225.         goboard[x][y].GroupNum = lowest;
  226.     }
  227.     /* Now fix the liberties of enemy groups adjacent to played stone */
  228.     FixLibs(color, x, y, PLACED);  /* Fix the liberties of opcolor */
  229.     ReEvalGroups(color, x, y, lowest);
  230.     RelabelGroups();
  231.     return TRUE;
  232. }
  233.  
  234. /* Remove a stone from the board */
  235. void
  236. GoRemoveStone(x, y)
  237.     short    x, y;
  238. {
  239.     goboard[x][y].Val = EMPTY;
  240.     goboard[x][y].GroupNum = 0;
  241.     removestone( x, y);
  242. }
  243.  
  244. /* Merges two groups -- Renumbers stones and deletes second group from
  245. list.  Fixes stone count of groups.  This does not fix anything else. 
  246. FixLibs must be called to fix liberties, etc. */
  247. void
  248. MergeGroups(g1, g2)
  249.     short    g1, g2;
  250. {
  251.     short    x, y;
  252.  
  253.  
  254.     ForeachPoint(y,x)
  255.         if (goboard[x][y].GroupNum == g2)
  256.             goboard[x][y].GroupNum = g1;
  257.     GroupList[g1].count += GroupList[g2].count;
  258.     DeleteGroup( g2 );  /* Removes group from GroupList */
  259. }
  260.  
  261. /* Stores a group code to be deleted */
  262. void
  263. DeleteGroup(code)
  264.     short    code;
  265. {
  266.     DeletedGroups[DeletedGroupCount++] = code;
  267. }
  268.  
  269. /* Re-evaluate the groups given the last move.  This assumes that the
  270. last move has been merged into adjoining groups and all liberty counts
  271. are correct.  Handles capture. Checks for Ko.  Keeps track of captured
  272. stones. code is the group number of the stone just played. */
  273. void
  274. ReEvalGroups(color, x, y, code)
  275.     enum bVal    color;
  276.     short        x, y, code;
  277. {
  278.     short        fgroups[4], egroups[4],
  279.             fcnt, ecnt, i, killcnt = 0, count = 0;
  280.     enum bVal    opcolor = BLACK;
  281.  
  282.     if (color == BLACK)
  283.         opcolor = WHITE;
  284.     /* Check for capture */
  285.     Connect( color, x, y, fgroups, &fcnt, egroups, &ecnt);
  286.     if (ecnt)
  287.     {
  288.         /* See if any of the groups have no liberties */
  289.         for (i = 0; i < ecnt; i++)
  290.             if (GroupList[egroups[i]].liberties == 0)
  291.             {
  292.                 killcnt++;
  293.                 count = GroupList[egroups[i]].count;
  294.                 GroupCapture( egroups[i]);
  295.             }
  296.     }
  297.     /* Check for ko.  koX and koY are set in GroupCapture above. */
  298.     if (killcnt == 1 && count == 1 && GroupList[ code  ].count == 1
  299.                 && GroupList[ code ].liberties == 1)
  300.     {
  301.         ko = TRUE;
  302.     }
  303.     if (killcnt)
  304.         intrPrisonerReport( blackPrisoners, whitePrisoners);
  305.     /* Set eye count for groups */
  306.     CountEyes();
  307. }
  308.  
  309. /* Remove a captured group from the board and fix the liberties of any
  310.    adjacent groups.  Fixes prisoner count. Sets KoX and KoY */
  311. /*-- update display of captured stones -neilb --*/
  312. void
  313. GroupCapture(code)
  314.     short    code;
  315. {
  316.     short    x, y;
  317.  
  318.     if (GroupList[code].color == BLACK)
  319.         blackPrisoners += GroupList[code].count;
  320.     else
  321.         whitePrisoners += GroupList[code].count;
  322.     intrPrisonerReport(blackPrisoners, whitePrisoners);
  323.     ForeachPoint(y,x)
  324.         if (goboard[x][y].GroupNum == code)
  325.         {
  326.             FixLibs(GroupList[code].color,x,y,REMOVED);
  327.             GoRemoveStone(x, y);
  328.             koX = x;
  329.             koY = y;
  330.         }
  331.     DeleteGroup( code);
  332. }
  333.  
  334. /* Fix the liberties of groups adjacent to x, y.  move indicates
  335.   whether a stone of color was placed or removed at x, y
  336.   This does not change liberty counts of friendly groups when a stone
  337.   is placed.  Does not do captures. */
  338. void
  339. FixLibs( color, x, y, move)
  340.     enum    bVal color;
  341.     short    x, y, move;
  342. {
  343.     short    fgroups[4], fcnt, egroups[4], ecnt, i;
  344.     enum    bVal opcolor = BLACK;
  345.  
  346.     if (color == BLACK)
  347.         opcolor = WHITE;
  348.     Connect( color, x, y, fgroups, &fcnt, egroups, &ecnt);
  349.     if (move == PLACED)
  350.         for (i = 0; i < ecnt; i++)
  351.             GroupList[egroups[i]].liberties--;
  352.     else /* Stone removed so increment opcolor */
  353.         for (i = 0; i < ecnt; i++)
  354.             GroupList[egroups[i]].liberties++;
  355. }
  356.  
  357. void
  358. goSetHandicap(handicap)
  359. {
  360.     if (handicap < 2)
  361.         return;
  362.  
  363.     GoPlaceStone(BLACK,3,3);
  364.     GoPlaceStone(BLACK,15,15);
  365.  
  366.     if (handicap >= 3)
  367.         GoPlaceStone(BLACK,15,3);
  368.     if (handicap >= 4)
  369.         GoPlaceStone(BLACK,3,15);
  370.     if (handicap == 5 || handicap == 7 || handicap == 9)
  371.         GoPlaceStone(BLACK,9,9);
  372.     if (handicap >= 6)
  373.     {
  374.         GoPlaceStone(BLACK,15,9);
  375.         GoPlaceStone(BLACK,3,9);
  376.     }
  377.     if (handicap >= 8)
  378.     {
  379.         GoPlaceStone(BLACK,9,15);
  380.         GoPlaceStone(BLACK,9,3);
  381.     }
  382. }
  383.  
  384. void
  385. goRestart(handicap)
  386.     int    handicap;
  387. {
  388.     register short        i;
  389.     register struct bRec    *gpt    = &goboard[0][0];
  390.  
  391.  
  392.     GroupCount = 0;
  393.     ko = FALSE;
  394.     blackPrisoners = whitePrisoners = 0;
  395.     intrPrisonerReport(0, 0);
  396.     for (i=0; i<361; gpt++,i++)
  397.     {
  398.         gpt->Val = EMPTY;
  399.         gpt->GroupNum = 0;
  400.     }
  401.     goSetHandicap(handicap);
  402. }
  403.  
  404.  
  405. /* if any groups have been deleted as a result of the last move, this
  406.    routine will delete the old group numbers from GroupList and
  407.    reassign group numbers. */
  408. void
  409. RelabelGroups()
  410. {
  411.     unsigned    short i, j, x, y;
  412.  
  413.     for (i = 0; i < DeletedGroupCount; i++)
  414.     {
  415.         /* Relabel all higher groups */
  416.         ForeachPoint(y,x)
  417.             if (goboard[x][y].GroupNum > DeletedGroups[i])
  418.                 goboard[x][y].GroupNum--;
  419.         /* Move the groups down */
  420.         for (y = DeletedGroups[i]; y < GroupCount; y++)
  421.             GroupList[y] = GroupList[y+1];
  422.         /* fix the group numbers stored in the deleted list */
  423.         for (j = i+1; j < DeletedGroupCount; j++)
  424.             if (DeletedGroups[j] > DeletedGroups[i])
  425.                 DeletedGroups[j]--;
  426.         GroupCount--;
  427.     }
  428. }
  429.  
  430. /* Returns liberty count for x, y intersection.  Sets marked to true
  431.    for each liberty */
  432. short
  433. CountAndMarkLibs( x, y)
  434.     short    x, y;
  435. {
  436.     short    tx,ty,i;
  437.     short    cnt = 0;
  438.  
  439.  
  440.     for (i=0;i<4;i++)
  441.     {
  442.                 tx = x + xVec[i];
  443.                 ty = y + yVec[i];
  444.                 if (LegalPoint(tx,ty) && goboard[tx][ty].Val == EMPTY
  445.                     && goboard[tx][ty].marked == FALSE)
  446.         {
  447.             cnt++;
  448.             goboard[tx][ty].marked = TRUE;
  449.         }
  450.     }
  451.     return cnt;
  452. }
  453.  
  454. /* Determine the number of liberties for a group given the group code
  455.    num */
  456. void
  457. CountLiberties( code)
  458.     short    code;
  459. {
  460.     short    x, y, libcnt = 0;
  461.  
  462.     ForeachPoint(y,x)
  463.         if (goboard[x][y].GroupNum == code)
  464.             libcnt += CountAndMarkLibs( x, y);
  465.     EraseMarks();
  466.     GroupList[code].liberties = libcnt;
  467. }
  468.  
  469. void
  470. CheckForEye( x, y, groups, cnt, recheck)
  471.     short    x, y, groups[4], cnt, *recheck;
  472. {
  473.     short    i;
  474.  
  475.     for (i = 0; i < (cnt-1); i++)
  476.         if (groups[i] != groups[i+1])
  477.         {
  478.             /* Mark liberty for false eye check */
  479.             goboard[x][y].marked = TRUE;
  480.             (*recheck)++;
  481.             return;
  482.         }
  483.     /* It is an eye */
  484.     GroupList[groups[i]].eyes += 1;
  485. }
  486.    
  487. /* Set the eye count for the groups */
  488. void CountEyes()
  489. {
  490.     short    i, x, y,
  491.         wgroups[4], bgroups[4], wcnt, bcnt, max, cnt, recheck = 0, eye;
  492.  
  493.     for (i = 1; i <= GroupCount; i++)
  494.         GroupList[i].eyes = 0;
  495.  
  496.     ForeachPoint(y,x)
  497.     {
  498.         if (goboard[x][y].Val != EMPTY)
  499.             continue;
  500.         cnt = Connect(WHITE,x,y,wgroups,&wcnt,bgroups,&bcnt);
  501.         max = Maxlibs( x, y);
  502.         if (cnt == max && wcnt == 1 && bcnt == 0)
  503.             GroupList[wgroups[0]].eyes++;
  504.         else if (cnt == max && bcnt == 1 && wcnt == 0)
  505.             GroupList[bgroups[0]].eyes++;
  506.         else if (cnt == max && ( bcnt == 0 || wcnt == 0 ))
  507.         {
  508.             goboard[x][y].marked = TRUE;
  509.             recheck++;
  510.         }
  511.     }
  512.  
  513.     /*-- Now recheck marked liberties to see if two or more one eye --*/
  514.     /*-- groups contribute to a false eye */
  515.     if (recheck == 0)
  516.         return;
  517.  
  518.     ForeachPoint(y,x)
  519.         if (goboard[x][y].marked)
  520.         {
  521.             recheck--;
  522.             goboard[x][y].marked = FALSE;
  523.             Connect( WHITE, x, y, wgroups, &wcnt, bgroups, &bcnt);
  524.             /* If all the groups have at least one eye then all the
  525.             groups are safe from capture because of the common
  526.             liberty at x, y */
  527.             eye = TRUE;
  528.             for (i = 0; i < wcnt; i++)
  529.                 if (GroupList[wgroups[i]].eyes == 0)
  530.                     eye = FALSE;
  531.             if (eye)
  532.                 for (i = 0; i < wcnt; i++)
  533.                     GroupList[wgroups[i]].eyes++;
  534.             for (i = 0; i < bcnt; i++)
  535.                 if (GroupList[bgroups[i]].eyes == 0)
  536.                     eye = FALSE;
  537.             if (eye)
  538.                 for (i = 0; i < bcnt; i++)
  539.                     GroupList[bgroups[i]].eyes++;
  540.             if (recheck == 0)
  541.                 return;
  542.         }
  543. }
  544.  
  545.  
  546. short    foo[19][19];
  547.  
  548. /*----------------------------------------------------------------
  549. -- CountUp()                            --
  550. --    Count up final scores at the end of the game.        --
  551. ----------------------------------------------------------------*/
  552. CountUp()
  553. {
  554.     short    x,y;
  555.     short    CountFromPoint();
  556.     short    vv;
  557.     int    btotal,wtotal;
  558.     char    buff[512];
  559.  
  560.  
  561.     blackTerritory = whiteTerritory = 0;
  562.     ForeachPoint(y,x)
  563.     {
  564.         goboard[x][y].marked = FALSE;
  565.         foo[x][y] = CNT_UNDECIDED;
  566.     }
  567.     ForeachPoint(y,x)
  568.         if (goboard[x][y].Val==EMPTY && foo[x][y]==CNT_UNDECIDED)
  569.         {
  570.             FillPoints(x,y,CountFromPoint(x,y));
  571.         }
  572.  
  573.     wtotal = whiteTerritory + blackPrisoners;
  574.     btotal = blackTerritory + whitePrisoners;
  575.  
  576.     showresult(whiteTerritory,blackPrisoners,blackTerritory,whitePrisoners);
  577.  
  578. /* XXX
  579.     sprintf(buff,"White : %3d territory + %3d prisoners = %d\n\
  580. Black : %3d territory + %3d prisoners = %d\n\n%s.",
  581.             whiteTerritory,blackPrisoners,wtotal,
  582.             blackTerritory,whitePrisoners,btotal,
  583.             (btotal>wtotal?"Black wins":(wtotal>btotal?"White wins":
  584.             "A draw")));
  585.     XtVaSetValues(message,XtNstring,buff,0);
  586. */
  587. }
  588.  
  589. void FillPoints(x,y,val)
  590.     short    x,y,val;
  591. {
  592.     int    i;
  593.     short    tx,ty;
  594.  
  595.  
  596.     if ((foo[x][y] = val) == CNT_BLACK_TERR)
  597.         blackTerritory++;
  598.     else if (val == CNT_WHITE_TERR)
  599.         whiteTerritory++;
  600.     for (i=0;i<4;i++)
  601.     {
  602.         tx = x + xVec[i];
  603.         ty = y + yVec[i];
  604.         if (!LegalPoint(tx,ty))
  605.             continue;
  606.         if (goboard[tx][ty].Val==EMPTY && foo[tx][ty]==CNT_UNDECIDED)
  607.             FillPoints(tx,ty,val);
  608.     }
  609. }
  610.  
  611. short
  612. CountFromPoint(x,y)
  613.     short    x,y;
  614. {
  615.     int    i;
  616.     short    tx,ty;
  617.     short    blkcnt=0,whtcnt=0;
  618.     short    baz;
  619.  
  620.  
  621.     goboard[x][y].marked = TRUE;
  622.     for (i=0;i<4;i++)
  623.     {
  624.         tx = x + xVec[i];
  625.         ty = y + yVec[i];
  626.         if (!LegalPoint(tx,ty))
  627.             continue;
  628.         if (goboard[tx][ty].Val == BLACK)
  629.             blkcnt++;
  630.         else if (goboard[tx][ty].Val == WHITE)
  631.             whtcnt++;
  632.         else
  633.         {
  634.             if (goboard[tx][ty].marked)
  635.                 continue;
  636.             baz = CountFromPoint(tx,ty);
  637.             if (baz == CNT_NOONE)
  638.                 return CNT_NOONE;
  639.             else if (baz == CNT_BLACK_TERR)
  640.                 blkcnt++;
  641.             else if (baz == CNT_WHITE_TERR)
  642.                 whtcnt++;
  643.         }
  644.         if (blkcnt && whtcnt)
  645.             return CNT_NOONE;
  646.     }
  647.     if (blkcnt && !whtcnt)
  648.         return CNT_BLACK_TERR;
  649.     else if (whtcnt && !blkcnt)
  650.         return CNT_WHITE_TERR;
  651.     else
  652.         return CNT_UNDECIDED;
  653. }
  654.